package com.dbh.alg.datastructure;

/**
 * 回文链表
 * @author 董帮辉
 * @date 2025/5/10
 **/
public class E09Leetcode234_回文链表 {

    /**
     * 判断是否是回文链表
     * @param head 链表头
     * @return true表示是 false表示否
     * <p>
     * 步骤1:找到中间点同时反转前半个链表
     * 步骤2:反转后的前半个链表 与 后半个链表逐一比较
     */
    public static boolean isPalindrome (ListNode head) {
        ListNode p1 = head; // 慢
        ListNode p2 = head; // 快
        ListNode n1 = null; // 新头
        ListNode o1 = head; // 旧头
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;

            // 反转链表
            o1.next = n1;
            n1 = o1;
            o1 = p1;
        }

        System.out.println(n1);

        if (p2 != null) {
            p1 = p1.next;
        }

        while (p1 != null) {
            if (p1.val != n1.val) {
                return false;
            }
            p1 = p1.next;
            n1 = n1.next;
        }
        return true;
    }



    public static void main(String[] args) {
        ListNode o1 = ListNode.of(1, 2, 2, 1);
        System.out.println(isPalindrome(o1));

        ListNode o2 = ListNode.of(1, 2, 3, 2, 2);
        System.out.println(isPalindrome(o2));
    }

}
